//: [Previous](@previous)

/*:
 # 插入排序
 * 最好情况 O(n))
 * 最坏情况 O(n^2))
 * 平均时间复杂度 O(n^2))
 * 空间复杂度 0(1)
 
 1. 从第一个元素开始，取出这个元素后的一个元素
 2. 比较这个元素,插入到排好的队列中
 3. 重复执行1，2步，直到最后一个元素
 
 */

import Foundation

var numbers = [3, 6, 5, 2, 7, 9, 1, 4, 3]
print("排序前 \(numbers)")

func insertSort(_ arr: [Int]) -> [Int] {
    if arr.count < 2 {
        return arr
    }
    
    var nums = arr
    
    for i in 1..<nums.count {
        var j = i
        let temp = nums[j]
        while j > 0 && temp < nums[j-1] {
            nums[j] = nums[j-1]
            j -= 1
        }        
        if j != i {
            nums[j] = temp
        }
    }
    
    return nums
}

print("插入排序后 \(insertSort(numbers))")

//: [Next](@next)
